package thinking.dynamic_programming;

/**
 * 优化DynamicProgramming
 * 使用一维数组
 *
 * @author yeyangtao created at 10:29 2020/10/20
 */
public class PackageQuestion1 {
    //weight:物品重量，n:物品个数，w:背包可承载重量
    public int knapsack(int[] weight, int n, int w) {
        // 默认值false
        boolean[] states = new boolean[w + 1];
        states[0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
        if (weight[0] <= w) {
            states[weight[0]] = true;
        }
        for (int i = 1; i < n; ++i) { // 动态规划状态转移
            //从后往前 防止前面的覆盖后面的数据
            for (int j = w - weight[i]; j >= 0; --j) {//把第i个物品放入背包
                if (states[j]) states[j + weight[i]] = true;
            }
        }
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[i]) return i;
        }
        return 0;
    }
}
